題目說明

實作資料結構 min stack，包含底下幾種操作 function

• push: 與 一般的 stack 相同
• pop: 與 一般的 stack 相同
• top：與 一般的 stack 相同
• getMin：拿到 stack 中最小的元素

每一個操作時間複雜度都必須是 O(1)

解題思路

這題需要兩個 stack ，一個 stack 支援普通 stack 的操作，一個 stack 用來維護最小值，使得 top 一定都是最小值

• push: 與 一般的 stack 相同，並且比較 min stack top 的值是否比 放入的 val 大，是的話就把預放入的 value 也 push 到 min stack 中
• pop: 與 一般的 stack 相同，加上判斷 min stack top 是不是跟 stack top 一樣，是的話也要將 min stack top pop 掉
• top：與 一般的 stack 相同
• getMin：拿到 min stack top

程式碼

class MinStack:

    def __init__(self):
        self.data_stack = []
        self.min_stack = []
        

    def push(self, val: int) -> None:
        self.data_stack.append(val)
        if not self.min_stack or self.min_stack[-1] >= val:
            self.min_stack.append(val)
        

    def pop(self) -> None:
        if self.data_stack:
            if self.data_stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
        self.data_stack.pop()
        

    def top(self) -> int:
        return self.data_stack[-1]
        

    def getMin(self)->int:
        return self.min_stack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()